package com.le.enhance.class6;

import org.junit.Test;

/**
 * 换钱的方法数
 * 【题目】
 * 给定数组arr，arr中所有的值都为正数且不重复。每个值代表
 * 一种面值的货币，每种面值的货币可以使用任意张，再给定一 个整数aim代表要找的钱数，求换钱有多少种方法。
 * 【举例】
 * arr=[5,10,25,1]，aim=0。 组成0元的方法有1种，就是所有面值的货币都不用。所以返回1。
 * arr=[5,10,25,1]，aim=15。 组成15元的方法有6种，
 * 分别为3张5元、1张10元+1张5元、1张 10元+5张1元、10张1元+1张5元、2张5元+5张1元和15张1元。所 以返回6。
 * arr=[3,5]，aim=2。 任何方法都无法组成2元。所以返回0。
 */
public class Code_01_CoinsWay {

    public static int getWays(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process1(arr, 0, aim);
    }

    private static int process1(int[] arr, int index, int aim) {
        int res = 0;
        if (index == arr.length) {
            res = aim == 0 ? 1 : 0;
        } else {
            for (int j = 0; arr[index] * j <= aim; j++) {
                res += process1(arr, index + 1, aim - arr[index] * j);
            }
        }
        return res;
    }

    @Test
    public void test(){
        int[] arr = {5,10,25,1};
        System.out.println(getWays(arr,15));
    }
}
